package com.tys.algorithm.bak.code2;

import com.tys.algorithm.advanced.code.class07.HeapGreater;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;


/**
 * 得奖系统规则：
 * 1如果某个用户购买商品数为0，又发生退货事件，认为该事件无效，得奖名单和之前事件一致
 * 2某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
 * 3.每次都是最多K个用户得奖，K也为传入的参数。
 * 如果根据全部规则，得奖数不够k个，就以不够的情况出结果
 * 4.得奖系统分为得奖区和候选区，任何用户只要购买数>0，一定在这两个区中的一个
 * 5.购买数量最大的前K名用户进入得奖区
 * 最初如果得奖区没有达K个用户，新来的直接进得奖区
 * 6.如果购买数不足以进入得奖区的用户，进入候选区
 * 7候选区购买数最多的用户，已经足以进入得奖区
 * 该用户替换得奖区中购买数最少的用户（大于才能替换）
 * 如果得奖区中购买数量最少用户有多个，替换最早进入得奖区的用户
 * 如果候选区中购买数量最多的用户有多个，机会给最早进入候选区的用户
 * 8.候选区和得奖区是两套时间
 * 用户只会在其中一个区域，只会有一个区域时间，另一个从得奖区出来进入候选区的用户，得奖区时间删除
 * 进入候选区的时间就是当前事件的时间，可以理解为arr[i]和top[i]中的i
 * 从候选区出来进入得奖区的用户，候选区时间删除
 * 进入得奖区的时间就是当前事件的时间
 * 9用户购买数==0，不管在哪个区都离开，区域时间删除，下次用户又发生购买行为，产生>0的购买数，根据之前规则回到某个区域中，进入时间重记
 * ​题目简化：
 * 1.用户购买数为0，发生退货，事件无效
 * 2.用户购买商品数+1，退货商品数-1
 * 3.<=K个用户得奖
 * 4.系统分得奖区和候选区，用户购买商品数>0
 * 5.得奖区：商品数最大的前k个数
 * 6.候选区：不满足得奖区的用户,
 * 7.候选区用户进入得奖区规则：
 * 多个用户时，看进入时间，机会给最早的
 * 8.候选区和得奖区两个时间
 * 从某个区进入另一个区，老时间删除，设置新时间
 * 9.用户购买数为0时，清空区域时间，下次重新计时和计数
 */
public class Code34_EveryStepShowBoss {
    //顾客类
    public static class Customer {
        public int id;//顾客id
        public int buy; //购买数量
        public int enterTime; //进入区时间

        public Customer(int v, int b, int o) {
            id = v;
            buy = b;
            enterTime = 0;
        }
    }

    //候选区比较器：买的多的，进入时间早的排前面，好的在前面
    public static class CandidateComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
        }

    }

    //得奖区：买的少的，进入时间早的排前面，差的前面
    public static class DaddyComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
        }

    }

    /**
     * 方法1：暴力法
     * 干完所有事，模拟不优化
     *
     * @param arr 顾客数组
     * @param op  对应顾客买还是卖
     * @param k   最大获奖人数
     * @return
     */
    public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {

        HashMap<Integer, Customer> map = new HashMap<>(); //顾客存储表id对应用户

        ArrayList<Customer> cands = new ArrayList<>(); //候选

        ArrayList<Customer> daddy = new ArrayList<>();//得奖区

        List<List<Integer>> ans = new ArrayList<>(); //获奖名单

        //循环顾客数组
        for (int i = 0; i < arr.length; i++) {
            int id = arr[i];//顾客id
            boolean buyOrRefund = op[i]; //买了还是退货了
            //退货并且当前用户表没有这个用户，获奖名单不变还是原来的
            //用户之前购买数=0，此时退货
            if (!buyOrRefund && !map.containsKey(id)) {
                //得到获奖名单
                ans.add(getCurAns(daddy));
                //继续遍历
                continue;
            }
            // 没有发生：用户购买数为0并且又退货了
            // 用户表中没有顾客
            // 用户之前购买数是0，此时买货事件
            // 用户之前购买数>0， 此时买货
            // 用户之前购买数>0, 此时退货
            if (!map.containsKey(id)) {
                map.put(id, new Customer(id, 0, 0)); //新建用户
            }
            // 买或卖
            Customer c = map.get(id);
            if (buyOrRefund) { //买
                c.buy++;
            } else { //卖
                c.buy--;
            }
            if (c.buy == 0) { //用户删除
                map.remove(id);
            }
            // 用户c
            // 下面做
            //新来的用户刚买：候选区和得奖区都没有
            if (!cands.contains(c) && !daddy.contains(c)) {
                if (daddy.size() < k) { //得奖区没满
                    c.enterTime = i;//设置时间
                    daddy.add(c); //直接进得奖区
                } else {
                    //得奖区满了：加入候选区
                    c.enterTime = i;
                    cands.add(c); //进候选区
                }
            }
            //清理候选区中购买数为0的顾客，为0的清理
            cleanZeroBuy(cands);
            //清理得奖区中购买数为0的顾客
            cleanZeroBuy(daddy);
            //得奖区和候选区排序
            cands.sort(new CandidateComparator());//候选区最好的放前
            //得奖区排序
            daddy.sort(new DaddyComparator());//得奖区最差放前
            //调整得奖区和候选区
            move(cands, daddy, k, i);//得奖区和候选区交换
            //获取获奖名单
            ans.add(getCurAns(daddy));
        }
        return ans;
    }

    //候选区用户替换得奖区用户
    public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
        if (cands.isEmpty()) { //候选区为空，不替换
            return;
        }
        // 候选区不为空有顾客
        //得奖区没满
        if (daddy.size() < k) {
            //获得候选区排名第一的顾客
            //候选区有用户，得奖区没满：得奖区用户买1个时又退货
            //拿到候选区0用户
            Customer c = cands.get(0);
            //设置时间
            c.enterTime = time;
            //加入得奖区
            daddy.add(c);
            //从候选区移除
            cands.remove(0);
        } else {
            // 得奖区满了，候选区有东西
            //候选区排名第一购买数量 > 得奖区排名第一的数量，替换
            //候选区买的最大数量大于得奖区买的最小数量
            if (cands.get(0).buy > daddy.get(0).buy) {
                //保存得奖区排名第一的顾客,获得得奖区
                Customer oldDaddy = daddy.get(0);
                //从删除得奖区排名第一的顾客,得奖区删除
                daddy.remove(0);
                //保存候选区排名第一的顾客,候选区
                Customer newDaddy = cands.get(0);
                //删除候选区排名第一的顾客,候选区删除
                cands.remove(0);
                //候选区顾客和得奖区顾客时间重置,设置新时间
                newDaddy.enterTime = time;
                oldDaddy.enterTime = time;
                //候选区第一名加入得奖区
                daddy.add(newDaddy);
                //得奖区第一名加入候选区
                cands.add(oldDaddy);
            }
        }
    }

    //清理数组中购买数量为0 的顾客
    public static void cleanZeroBuy(ArrayList<Customer> arr) {
        //临时存储购买数不为0的表
        List<Customer> noZero = new ArrayList<Customer>();
        //遍历数组找到购买数不为0 的顾客，加入临时数组
        for (Customer c : arr) {
            if (c.buy != 0) {
                noZero.add(c);
            }
        }
        //清空原数组
        arr.clear();
        //将临时数组中数据拷贝到原数组
        for (Customer c : noZero) {
            arr.add(c);
        }
    }

    //得到获奖名单：将得奖区所有用户遍历出来
    public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
        List<Integer> ans = new ArrayList<>();
        for (Customer c : daddy) {
            //加入获奖名单
            ans.add(c.id);
        }
        return ans;
    }


    /**
     * 方法2：使用堆，优化
     *
     * @param arr 顾客数组
     * @param op  对应顾客买还是卖
     * @param k   最大获奖人数
     * @return
     */
    public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
        List<List<Integer>> ans = new ArrayList<>();//答案
        WhosYourDaddy whoDaddies = new WhosYourDaddy(k);
        for (int i = 0; i < arr.length; i++) {
            whoDaddies.operate(i, arr[i], op[i]);
            ans.add(whoDaddies.getDaddies());
        }
        return ans;
    }

    //堆结构
    public static class WhosYourDaddy {
        private HashMap<Integer, Customer> customers; //顾客表
        private HeapGreater<Customer> candHeap;//候选区加强堆
        private HeapGreater<Customer> daddyHeap;//得奖区加强堆
        private final int daddyLimit; //得奖区大小限制

        //构造函数初始化
        public WhosYourDaddy(int limit) {
            customers = new HashMap<Integer, Customer>();
            //候选区大根堆：购买数大排上面，时间早排上面
            candHeap = new HeapGreater<>(new CandidateComparator());
            //得奖区小根堆：购买数少排上面，时间早排上面
            daddyHeap = new HeapGreater<>(new DaddyComparator());
            daddyLimit = limit;
        }

        /**
         * 当前处理 i 号事件， arr[i] -> 顾客id， buyOrRefund买或卖
         *
         * @param time        当前时间
         * @param id          顾客id
         * @param buyOrRefund 买还是卖
         */
        public void operate(int time, int id, boolean buyOrRefund) {
            //退货，顾客表中没有,两个区都没有
            if (!buyOrRefund && !customers.containsKey(id)) {
                return;
            }
            //新用户：顾客表中没有
            if (!customers.containsKey(id)) {
                //新建顾客
                customers.put(id, new Customer(id, 0, 0)); //新建用户
            }
            //得到顾客用户
            Customer c = customers.get(id);
            if (buyOrRefund) {
                c.buy++; //买
            } else {
                c.buy--; //卖
            }
            //购买数量为0则删除用户
            if (c.buy == 0) {
                customers.remove(id);
            }
            //上面都是O(1)
            //下面开始优化：O(logN)
            //得奖区和候选区都没有顾客c
            if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
                //当前用户得奖区没有，候选区也没有
                //得奖区没满：直接加入得奖区
                if (daddyHeap.size() < daddyLimit) {
                    //得奖区数量不够
                    c.enterTime = time;
                    daddyHeap.push(c);
                } else {
                    //得奖区满了：放候选区
                    c.enterTime = time;
                    candHeap.push(c);
                }
            } else if (candHeap.contains(c)) {
                //候选区中有顾客c
                //购买数为0
                if (c.buy == 0) {
                    //从候选区中删除顾客
                    candHeap.remove(c);//clog(N)
                } else {
                    //重新调整候选区堆中c的位置
                    candHeap.resign(c);//调整堆log(N)
                }
            } else {
                //得奖区中有顾客c
                //购买数为0
                if (c.buy == 0) {
                    //从得奖区删除顾客
                    daddyHeap.remove(c);//log(N)
                } else {
                    //重新调整得奖区堆中c的位置
                    daddyHeap.resign(c);//调整堆log(N)
                }
            }
            //是否移动得奖区和候选区，调整得奖区和候选区的顾客
            daddyMove(time);
        }

        //得到获奖名单：将得奖区所有用户遍历出来
        public List<Integer> getDaddies() {
            //得奖区所有顾客
            List<Customer> customers = daddyHeap.getAllElements();
            List<Integer> ans = new ArrayList<>();
            //全部加入获奖名单
            for (Customer c : customers) {
                ans.add(c.id);
            }
            return ans;
        }

        //移动候选区和得奖区
        private void daddyMove(int time) {
            //候选区为空不需要调整
            if (candHeap.isEmpty()) {
                return;
            }
            //得奖区没有满则直接加入得奖区
            if (daddyHeap.size() < daddyLimit) {
                //得奖区没满，将候选区放入得奖区
                Customer p = candHeap.pop();
                p.enterTime = time;
                daddyHeap.push(p);
            } else {
                //得奖区最后的最差和候选区的最好比较，如果候选区的好，则交换
                //得奖区满了
                //候选区中排名第一顾客购买数 > 得奖区中排名第一顾客购买数
                if (candHeap.peek().buy > daddyHeap.peek().buy) {
                    //保存得奖区第一名顾客
                    Customer oldDaddy = daddyHeap.pop();
                    //保存候选区第一名顾客
                    Customer newDaddy = candHeap.pop();
                    //重置时间
                    oldDaddy.enterTime = time;
                    newDaddy.enterTime = time;
                    //交换顾客
                    daddyHeap.push(newDaddy);
                    candHeap.push(oldDaddy);
                }
            }
        }

    }


    //--------------test----------------------
    //顾客购物类：存储顾客和顾客购买还是退货标记
    // 为了测试
    public static class Data {
        public int[] arr;//顾客数组
        public boolean[] op;//购买和退货标记数组

        public Data(int[] a, boolean[] o) {
            arr = a;
            op = o;
        }
    }

    //随机一个顾客购物类
    public static Data randomData(int maxValue, int maxLen) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        boolean[] op = new boolean[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * maxValue);//随机顾客id
            op[i] = Math.random() < 0.5 ? true : false;//随机是买还是退货
        }
        return new Data(arr, op);
    }

    // 对比两个获奖名单是否相等
    public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
        if (ans1.size() != ans2.size()) {
            return false;
        }
        for (int i = 0; i < ans1.size(); i++) {
            List<Integer> cur1 = ans1.get(i);
            List<Integer> cur2 = ans2.get(i);
            //长度不同则不相等
            if (cur1.size() != cur2.size()) {
                return false;
            }
            //升序：从小到大排序
            cur1.sort((a, b) -> a - b);
            cur2.sort((a, b) -> a - b);
            //遍历数组
            for (int j = 0; j < cur1.size(); j++) {
                if (!cur1.get(j).equals(cur2.get(j))) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int maxValue = 10;
        int maxLen = 100;
        int maxK = 6;
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            Data testData = randomData(maxValue, maxLen);
            int k = (int) (Math.random() * maxK) + 1;
            int[] arr = testData.arr;
            boolean[] op = testData.op;
            List<List<Integer>> ans1 = topK(arr, op, k);
            List<List<Integer>> ans2 = compare(arr, op, k);
            if (!sameAnswer(ans1, ans2)) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.println(arr[j] + " , " + op[j]);
                }
                System.out.println(k);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("出错了！");
                break;
            }
        }
        System.out.println("测试结束");
    }

}
